c(d,k) = (n^k-1) / (n^d-1). For example, the system G(2,6) inherits the nested systems G(2,1), G(2,2) a G(2,3);
G(2,1) is also nested into G(2,2) and G(2,3).
An algebraic theory of chord structures is being presented in this paper. Every tone grouping is depicted as an instance of the so-called G-system. The aim is to provide a simple algorithm for a generation of musical structures. It should be useful for programmers of computer music as well as for those interested in musical analysis. The theory of G-systems gives some known mathematical results in a simple and clearly organized way. Therefore it might be inspiring for mathematicians studying methods of enumeration, theory of groups, algebraic solutions of combinatorial problems and other areas (Fermat's theorems, Gauss's theory of equation classes, Polya's enumeration, Sylowov's groups,..).
Let us think about arranging n elements into k cells. Let A be a set with n members (elements) and the set E(A) = {0, 1, .., n-1} the base of A. Let B be a set with k members (cells) and ξ relation from E(B) to E(A).
ξ
(cells) E(B) ------------- E(A) (elements)
Let numbers E(B) be positions of numbers (digits) from E(A). Written in
n-number system we obtain n^k possible numbers. Let the set of all these
numbers be marked M()= M(n,k). Members of this set are so called instances.
E.g. the sets A={p, q}, B={x, y, z} have E(A)={0, 1}, E(B)={0, 1, 2} as
their bases. The system M(2,3) has 2^3=8 instances {000, 001,.., 111}.
Let us call the set M()=M(n,k) (with relation ξ) system of degree n and
order k. If ξ is equivalence relation one can distinguish some instance
classes. The classes are the result of decay M()/ξ. Each class has its
representative number. Number of transpositions means the number of members in
a class.
In case of 12-tone tempered musical system we have n=2, k=12. E.g. let
A={exist, non-exist} and B={c, c#, d, d#, e, f, f#, g, g#, a, a#, h} . The
bases E(A)={0, 1}, E(B)={0, 1, .., 11} and the ξ relation forms the system
M(2,12). The instance 001001001001 represents tone groupings [c, d#, f#, a] and
has two transpositions 010010010010, i.e. [c#, e, g, a#] and 100100100100 i.e.
[d, f, g#, h]. The diminished seventh chord is a class of M(2,12) with 3
transpositions.
Let relation G, defined as follows, be called G-relation.
u(i,j) = n^j * g(i) ( mod(r-1))
Number r is (in this article) always assumed to be equal to the total number of instances, i.e. r = n^k. Number g(i) is representative number, u(i,j) are instance numbers.
Systems with the G-relation we name G-systems, G()=G(n,k). Every G(n,k) has m(n,k) classes marked g(i), i=1..m.
Let us write an outline of all instances ordered by classes. The outline of G(n,k) has k columns (k is the maximum transposition count). The 16 instances of G(2,4) make 6 classes.
Instances of G(2,4)
1/ 0 0 0000 0
0 0
2/ 0 0 0 1 1 0 0 0 0001 0010 0100 1000 1 2 4 8
0 1 0 0 0 0 1 0
3/ 0 1 1 1 1 0 0 0 0011 0110 1100 1001 3 6 12 9
0 1 0 0 1 0 1 1
4/ 1 0 0 1 0101 1010 5 10
0 1 1 0
5 1 1 1 1 1 0 0 1 0111 1110 1101 1011 7 14 13 11
0 1 1 0 1 1 1 1
6/ 1 1 1111 15
1 1
The algorithm is similar to the Eratosthenes's sieve for separating primes from natural numbers. In our case we separate numbers of classes representatives from all instance numbers. Instance transpositions are analogies of prime multiples in Eratosthenes's sieve.
empty set M
|
+--+- for g=0 to (n^(k-1)-1) -- write the last class
| | | g=n^k-1
| ^ is class g in M ?
| | |
| +- YES-----+
| |NO
| |
| write g to M
| |
| instance u <- g
| |
|+---> while not u in M ----+
|| | |
|| write u to M |
|| | |
|| instance transposition |
|| u <- n * u |
|+------<-----+ |
+-------------<-------------+
Examples of the output:
G(2,1) G(3,1) G(4,1)
0 0 0
1 1 1
2 2
3
G(2,2) G(3,2) G(4,2)
0 0 0 6 9
1 2 1 3 1 4 7 13
3 2 6 2 8 10
4 3 12 11 14
5 7 5 15
8
G(2,3) G(3,3) G(4,3)
0 0 0 21
1 2 4 1 3 9 1 4 16 22 25 37
3 6 5 2 6 18 2 8 32 23 29 53
7 4 12 10 3 12 48 26 41 38
5 15 19 5 20 17 27 45 54
7 21 11 6 24 33 30 57 39
8 24 20 7 28 49 31 61 55
13 9 36 18 42
14 16 22 10 40 34 43 46 58
17 25 23 11 44 50 47 62 59
26 13 52 19 63
14 56 35
15 60 51
Instance number u(i,j) is prime relative to r -1 = n^k -1 only if
corresponding class number g(i) is prime relative to r -1. The number of all
instances that are primes relative to r -1 is φ(r), where φ is the Euler
function. If g(i) is prime relative to r -1, then its class must be the self
class (not nested) and such class has k instances.
Therefore: φ(n^k -1)= 0 (mod k)
In G(2,4) only these instances are prime numbers relative to 2^4 -1=15: (1,
2, 4, 8) and (7, 14, 13, 11). And φ(2^4 -1) = φ(15) = 8; 8 = 0 (mod 4).
more
One of the first solutions to the problem we are studying was published by Gauss in his algebraic theory of equation classes [Gauss,1959]. Polya presented a general combinatorial solution of counting structures. His theorem of enumeration [Preparata,1974] was designed for counting of classes with regard to arbitrary operations of symmetry. Musical chord structures have only one such operation - rotation. This fact allows us to apply a simple algorithm.
For each d|k there exists a system G(n,d) nested to the G(n,k). The nested
class g' in G(n,k) is similar to its original class g from G(n,d). Truly
original classes are called self-classes. The similarity to the original
classes means the same number of transpositions and similar instance
structures. The system G(n,p), p is prime, has just one nested system G(n,1).
For g from G(n,d), g' from G(n,k), d|k it holds: g' = c . g where c is nesting
quotient defined as follows:
c(d,k) = (n^k-1) / (n^d-1). For example, the system G(2,6) inherits the
nested systems G(2,1), G(2,2) a G(2,3);
G(2,1) is also nested into G(2,2) and G(2,3).
Other example: the system G(2,4) inherits the nested systems G(2,1) and G(2,2); see e.g. class g(2) = 1 in G(2,2) and its corresponding class g(4) = 5 in G(2,4) with nesting quotient c(2,4) = 5.
G(2,1):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1
G(2,2):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1 u(1,2)= 2
g(3)= u(0,3)= 3
G(2,4):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1 u(1,2)= 2 u(2,2)= 4 u(3,2)= 8
g(3)= u(0,3)= 3 u(1,3)= 6 u(2,3)=12 u(3,3)= 9
g(4)= u(0,4)= 5 u(1,4)=10
g(5)= u(0,5)= 7 u(1,5)=14 u(2,5)=13 u(3,5)=11
g(6)= u(0,6)=15
Nesting quotients:
G(2,1) - G(2,2): c(1,2) = (2^2 -1) / (2^1 -1) = 3
G(2,2) - G(2,4): c(2,4) = (2^4 -1) / (2^2 -1) = 5
Let v(n,k), w(n,k) and m(n,k) be the number of self, nested and all classes
in G(n,k). It is hold:
Specially for prime p is:
E.g. The system G(2,6) has 14 classes (9 self-classes + 5 nested-classes):
Counting of classes in G(2,6)
|
Self classes |
Nested classes |
|
v(2,1)=2/1=2 |
w(2,1) = 0 |
|
v(2,2)=(2^2-1v(2,1))/2= 1 |
w(2,2) = v(2,1) = 2 |
|
v(2,3)=(2^3-1v(2,1))/3= 2 |
w(2,3) = v(2,1) = 2 |
|
v(2,6)=(2^6-1v(2,1)-2*v(2,2)-3*v(2,3))/6 = 9 |
w(2,6) = v(2,1)+v(2,2)+v(2,3)= 5 |
Therefore m(2,6)= v(6) +w(6) = 9 +5 = 14 classes.
Gauss [CG1} has put the previous recurrent equations in an elegant, compact form: n^k = ∑ d(d) i.e. in our terminology: n^k = ∑{d|k} d*v(n,d).
Let us evaluate the totals of all classes m(n,k) for particular orders k as functions of n:
k=1: m(n,1)= 1/1 (n) + 0 = n
k=2: m(n,2)= 1/2 (n^2- n)+ n = 1/2 (n^2+n)
k=3: m(n,3)= 1/3 (n^3-n)+ n = 1/3 (n^3+ 2n)
k=4: m(n,4)= 1/4 (n^4-n2)+ 1/2 (n^2+n) = 1/4 (n^4+ n^2+2n)
k=5: m(n,5)= 1/5 (n^5-n) + n = 1/5 (n^5+ 4n)
k=6: m(n,6)= 1/6 (n^6-n^3-n^2+n)+1/6(2n^3+3n^2+n)= 1/6 (n^6+n^3+2n^2+2n)
k=7: m(n,7)= 1/7 (n^7-n) + n = 1/7 (n^7+ 6n)
k=8: m(n,8)= 1/8 (n^8-n^4)+ 1/4(n^4+n^2+2n)=1/8(n^8+n^4+2n^2+4n)
In case of rotational operations Polya's theory gives this result [Beckenbach,1964]:
m(n,k) = 1/k ∑{d|k} φ(d)* n^{k/d} (including d=k),
where φ is the Euler function.
The nesting (shown in the previous paragraphs) is a matter of G-systems with
constant n.
Now we are going to study G-systems with constant k. These systems also have
something in common.
E.g. let us see the systems G(2,2) and G(3,2). The latter is only an extension
of the former.
G(3,2) as an extension of G(2,2)
G(2,2) = G(3,2) 0 0 1 2 1 3 3 4 6 2 7 5 8 |
Every G(n,k) has n classes nested from G(n,1). Let us assume, these classes
separate the G-system into segments. Let s (s
g(s) = (n-s) * (n^k-1) / (n-1).
If a segment exists in G(n,k) then a similar segment exists also in G(n+1,k).
This idea becomes clearer if we rewrite all the numbers u with the numbers
(n^k-1)-u.
Segmentation of G(3,3)
u 0 segment 2 1 3 9 2 6 18 4 12 10 5 15 19 7 21 11 8 24 20 ------------------ 13 segment 1 14 16 22 17 25 23 ------------------ 26 segment 0 |
(n^k-1)-u = 27-u 0 segment 0 ------------------ 9 1 3 12 10 4 13 segment 1 ------------------ 18 2 6 19 5 15 21 11 7 22 14 16 24 20 8 25 23 17 26 segment 2 |
Let us write the numbers n^k-1-u from the previous table as functions of n and take interest in quotients of the polynomials:
k=2 k=3
segment 0 segment 0
1 1
segment 1 segment 1
n 1 n^2 1 n
n+1 n^2+n n^2+1 n +1
n^2+n+1
The quotients of these polynomials are:
k=2 k=3
segment 0 segment 0
0 0 0 0 0
segment 1 segment 1
1 0 0 1 1 0 0 0 0 1 0 1 0
1 1 1 1 0 1 0 1 0 1 1
1 1 1
Each G-system is a set of numbers from the n-th number system. The G-relation separates G(n,k) into n segments, where every segment s uses always just s symbols, s=0..n-1.
Compositions of G-systems
G(1,2) 00 00 00 ---------------------------- 10 01 10 01 10 01 G(2,2) 11 11 11 ---------------------------- 20 02 20 02 20 02 21 12 21 12 21 12 G(3,2) 22 22 22 ---------------------------- 30 03 30 03 31 13 31 13 32 23 32 23 G(4,2) 33 33 ---------------------------- 40 04 41 14 42 24 43 34 G(5,2) 44 ---------------------------- |
G(1,3) 000 000 000 -------------------------------------------- 100 001 010 100 001 010 100 001 010 110 101 011 110 101 011 110 101 011 G(2,3) 111 111 111 -------------------------------------------- 200 002 020 200 002 020 201 012 120 201 012 120 210 102 021 210 102 021 211 112 121 211 112 121 220 202 022 220 202 022 221 212 122 221 212 122 G(3,3) 222 222 -------------------------------------------- 300 003 030 301 013 031 302 023 032 310 103 130 311 113 131 312 123 132 320 203 230 321 213 231 322 223 232 330 303 330 331 313 331 332 323 332 G(4,3) 333 -------------------------------------------- |
The sum of polynomial quotients is the same for all instances of a given class (the instances of a class have the same level).
Binary system G(2,k) is a special case of G-system, n=2. It is suitable for classification of musical structures.
In a binary system (base E(A) ={0, 1}) it is easy to express structure of
instances.
Let level of class L be the number of digits "1" in an
instance and let interval be the distance between two digits
"1". Distance schema is the list of all neighboring intervals, last
interval in brackets, [Janecek,1959].
Distance schema of instances in G(2,4))
i g(i) Instance numbers (binary) Schema Level ------------------------------------------------------ 1 0 0000 (0) 0 2 1 0001 0010 0100 1000 (4) 1 3 3 0011 0110 1100 1001 1(3) 2 4 5 0101 1010 2(2) 2 5 7 0111 1110 1101 1011 1 1(2) 3 6 15 1111 1 1 1 (1) 4 |
The last column in the previous table displays the level of the corresponding class i.e. level of instances of the class. Let us count how many instances and classes there are on each level.
Counting in G(2,4)
Level 0 1 2 3 4 ----------------------------------------- All instances 1 4 6 4 1 Nested instances 1 0 2 0 1 Self instances 0 4 4 4 0 ----------------------------------------- All classes 1 1 2 1 1 Nested classes 1 0 1 0 1 Self classes 0 1 1 1 0 |
The following diagrams display the same (structured into triangles) for all
G(2,k). The first column displays the order k of given G-system, in the next
columns are the counts for particular levels. The last columns have the totals
of instances or classes. The triangles are symmetrical, we write only half of
them.
E.g. in 12-tone music there are 220 triads in 19 classes. These 19 classes
mean that 19 types of triads exist (minor, major, augmented, diminished, ...).
One class only (the augmented triad) is nested. This class has 4 instances.
Therefore there is 220-4=216 self-instances of triads and 216/12 = 19-1 = 18
self-classes of triads.
k (0)(1)(2)(3) (4) (5) (6) (7) (8) (9)(10)(11)(12)
----------------------------------------------------------------------
12 1 12 66 220 495 792 924 792 495 220 66 12 1 all instances
----------------------------------------------------------------------
1 1 1
2 0 2 0
3 0 3 3 0 nested instances
4 0 4 4 4 0
6 0 6 12 18 12 6 0
----------------------------------------------------------------------
12 0 12 60 216 480 792 900 792 480 216 60 12 0 self instances
12 0 1 5 18 40 66 75 66 40 18 5 1 0 self classes
----------------------------------------------------------------------
1 1 1
2 0 1 0
3 0 1 1 0 nested classes
4 0 1 1 1 0
6 0 1 2 3 2 1 0
----------------------------------------------------------------------
12 1 1 6 19 43 66 80 66 43 19 6 1 1 all classes
Self-instance and self-classes triangle
|
|
|
Nested instance and nested classes triangle
|
|
|
All instance (Pascal triangle) and all classes triangle
|
|
|
The total number of nested instances as well as nested classes in a system
with prime k is equal to 2. Number of self-instances is always the k-multiple
of the number of self-classes.
more
In this paper we presented an insight into the problem of musical
structures. Our results were compared with similar results obtained by Gauss
and by Polya. The theory of G-systems also has some connections to others
mathematical areas.
E.g. a restriction of
G-systems (r<n^k) leads to the theory of primitive roots; the distribution of prime numbers in
particular classes might give some information about primes;...
Particularly, the triangle
of self-classes might be interesting. Some theorems about primes
(Wilson theorems,...) are connected with its structure. The triangle seems to
be more general then Pascal triangle - the latter can be obtained by an
integration of members from the former.
The theory of G-systems was presented at the poster session of the
Conference on Computational and Mathematical Methods in Music, Vienna, December
1-4, 1999 (Diderot Forum on Mathematics and Music). The text, which follows,
covers and extends the one printed in the conference proceedings.
At the beginning I called these systems by a term "Genetic systems",
because of certain analogy with inheritance (see Nesting of G-systems). Later I
have shortened the name to "G-systems". I worked on this theory
mostly in the years 1990-1992. In the following years, 1993-1996, I looked for
a similar theories in the literature.
The enumeration of total number of G-system classes is the same as the
enumeration of total number of equation classes, which was studied by Carl
Fridrich Gauss nearly 200 years ago. So the letter G in the name
"G-system" would be connected with Gauss. He was probably the first
one who knew and described these mathematical constructions.
Gauss,1959 Gauss Carl Fridrich: Trudy po teorii cisel (Ucenie o
vycetach II),p.782) (Works on Theory of Numbers; in Russian), Moscow 1959.
Janecek,1959 Janeček Karel: Základy moderní harmonie
(Fundamentals of Modern Harmony; in Czech), Prague 1965.
Beckenbach,1964 Edwin F.Beckenbach, George Polya: Applied
Combinatorial Mathematics University of California, John Wiley and Sons,Inc
, New York, 1964.
Preparata,1974 Franco P.Preparata, Raymond T.Yeh Introduction of
Discrete Structures Addison-Wesley Publishing Company Inc., U.S.A., 1974.
